package cn.qyd.leecode;

/**
 * @author 邱运铎
 * @date 2024-04-17 22:15
 */
public class BadNodeInfectII02 {

    public static void main(String[] args) {
        BadNodeInfectII02 demo = new BadNodeInfectII02();
        int[][] graph = new int[][]{{1,1,0,0,0,0,0,0,0},
                {1,1,0,0,0,0,0,0,0},
                {0,0,1,1,0,0,0,0,0},
                {0,0,1,1,1,0,0,0,0},
                {0,0,0,1,1,0,0,0,0},
                {0,0,0,0,1,1,0,0,0},
                {0,0,0,0,0,0,1,1,0},
                {0,0,0,0,0,0,1,1,1},
                {0,0,0,0,0,0,0,1,1}};
        int[] initial = new int[]{0,1,3,5};
        int i = demo.minMalwareSpread(graph, initial);
        System.out.println(i);
    }

    private int originBadNode;
    private int infectNodeNum;
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        boolean[] isInitial = new boolean[n];
        int minNodeId = n;
        for (int i : initial) {
            isInitial[i] = true;
            minNodeId = Math.min(minNodeId, i);
        }

        boolean[] visited = new boolean[n];
        // 记录每个最初感染节点 假如在移除后可以减少的 最终的感染节点数
        int[] infectNodeCount = new int[n];
        /**
         * 计算每个节点（不包括最初感染节点）的状态，有如下几个状态
         * 情况一： 通过该节点链接的节点中集合中没有最初感染节点，即该节点始终是正常的， 那么originBadNode = -1
         * 情况二： 通过该节点链接的节点中集合中只存在一个感染节点，说明一旦移除对应的感染节点，那个该节点最终会使正常的， 那么originBadNode = 该感染节点ID
         * 情况三： 通过该节点链接的节点集合中存在两个或以上的感染节点，此时仅移除某一个节点，无法阻止该节点最终变为感染节点，那么orinBadNode = -2
         *
         */
        for (int i = 0; i < n; i++) {
            if (visited[i] || isInitial[i]) {
                continue;
            }

            originBadNode = -1;
            infectNodeNum = 0;
            dfs(graph, i, visited, isInitial);
            /**
             * 当前属于情况二。 该节点的链接集合中只有一个最初感染节点
             */
            if (originBadNode >= 0) {
                /**
                 * 将该最初感染节点影响数 加上当前的节点连接集合大小
                 * 这里使用 += ，是因为可能存在多个节点的连接集合中只存在的最初感染节点为同一个，
                 * 所以需要使用 += 来获取该最初感染节点最终可影响的所有节点数量
                 */
                infectNodeCount[originBadNode] += infectNodeNum;
            }
        }

        //默认所有的最初感染节点影响的最终节点数一样，这样移除感染节点中最下的节点id。
        int removeNodeId = minNodeId;
        int maxInfectNodeCount = 0;
        for (int id :initial) {
            // 比较每个感染节点最终影响节点数，如果大于最大影响节点数，或者和最大影响节点数相同并且节点id小于removeNodeId就更新removeId和最大影响节点数
            if (infectNodeCount[id] > maxInfectNodeCount || (infectNodeCount[id] == maxInfectNodeCount && id < removeNodeId)) {
                removeNodeId = id;
                maxInfectNodeCount = infectNodeCount[id];
            }
        }
        return removeNodeId;
    }

    public void dfs(int[][] graph, int node, boolean[] visited, boolean[] isInitial) {
        visited[node] = true;
        infectNodeNum++;

        for (int i = 0; i < graph[node].length; i++) {
            // i 节点和node节点不可达，或者 i节点已访问，跳过
            if (graph[node][i] == 0 || visited[i]) {
                continue;
            }
            // 如果当前节点是最初感染节点，不会继续深搜，停下来做判断，从而更新originBadNode的值
            if (isInitial[i]) {
                // originBadNode != i 是为了通过不同路径防止多次找到了同一个最初感染节点
                // 例如 1 -> 2 和 1 -> 3 -> 2. 假如2是感染节点，那么会找到2两次，使originBadNode的值不正确。
                if (originBadNode != -2 && originBadNode != i) {
                    originBadNode = originBadNode == -1 ? i : -2;
                }
            } else {
                // 继续深搜，找到所有可达节点
                dfs(graph, i, visited, isInitial);
            }
        }
    }
}
